import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-08-26
 * Time: 22:26
 */

public class Solution {

    /**
     *  方法一: 纵向遍历
     */
    public String longestCommonPrefix1(String[] strs) {
        StringBuilder stringBuilder = new StringBuilder();
        int minLen = strs[0].length();
        for (int i = 0;i < strs.length;i++) {
            minLen = Math.min(strs[i].length(), minLen);
        }
        for (int i = 0;i < minLen;i++) {
            char c = strs[0].charAt(i);
            for (int j = 1;j < strs.length;j++) {
                if (strs[j].charAt(i) != c) {
                    return stringBuilder.toString();
                }
            }
            stringBuilder.append(c);
        }
        return stringBuilder.toString();
    }

    /**
     *  方法二: 对数组排序, 然后直接比较第一个和最后一个
     *  不过注意, 字符串数组排序时间复杂度很高, l*n*logn
     */
    public String longestCommonPrefix2(String[] strs) {
        Arrays.sort(strs);
        String begin = strs[0];
        String end = strs[strs.length-1];
        int minLen = Math.min(begin.length(), end.length());
        int i = 0;
        for (;i < minLen;i++) {
            if (begin.charAt(i) != end.charAt(i)) {
                break;
            }
        }
        return begin.substring(0, i);
    }


    /**
     *  方法三: 二分查找
     *  找到最短的长度, 那么公共前缀的 长度的范围就是 (0, minLen)
     *  然后二分, 每次都判断该长度是不是 公共前缀
     *  同样, 时间复杂度为 l*n*logn
     *  不过思想可以借鉴
     */
    public String longestCommonPrefix3(String[] strs) {
        int minLen = strs[0].length();
        for (int i = 0;i < strs.length;i++) {
            minLen = Math.min(strs[i].length(), minLen);
        }
        int left = 0;
        int right = minLen - 1;
        while (left <= right) {
            int mid = ((right-left)>>1) + left;
            if (isCommonPrefix(strs, mid)) {
                left = mid+1;
            } else {
                right = mid-1;
            }
        }
        return strs[0].substring(0, left);
    }

    public boolean isCommonPrefix(String[] strs, int index) {
        for (int i = 0;i <= index;i++) {
            char c = strs[0].charAt(i);
            for (int j = 1;j < strs.length;j++) {
                if (strs[j].length() <= i || strs[j].charAt(i) != c) {
                    return false;
                }
            }
        }
        return true;
    }
}
